#include<iostream>
using namespace std;
const int MOD = 1e9;
const int maxn= 1e6+7;
long long dp[maxn];
int n;
int main() {
  cin>>n;
  dp[1]=1;
  dp[2]=2;
  for(int i=3; i<=n; ++i) {
    dp[i] = dp[i-1];
    i++;
    dp[i] = (dp[i-1]+dp[i>>1])%MOD;
  }
  cout<<dp[n]<<'\n';
  return 0;
}
